package org.jbrisk;

import java.lang.reflect.Array;

public class TopologicalSorter<T> {

	private T[] vertexList; // list of vertices

	private int matrix[][]; // adjacency matrix

	private int numVerts = 0; // current number of vertices

	private T[] sortedArray;

	@SuppressWarnings("unchecked")
	public TopologicalSorter(Class<T> type, int size) {

		if (size <= 0)
			throw new IllegalArgumentException("Size must be greater than zero!");

		vertexList = (T[]) Array.newInstance(type, size);
		sortedArray = (T[]) Array.newInstance(type, size); // sorted vertex
															// labels

		initializeMatrix(size);
	}

	private void initializeMatrix(int size) {

		matrix = new int[size][size];

		for (int i = 0; i < size; i++)
			for (int k = 0; k < size; k++)
				matrix[i][k] = 0;
	}

	public void addVertex(T name) {

		vertexList[numVerts++] = name;
	}

	public void addEdge(int start, int end) {

		if (matrix == null)
			initializeMatrix(numVerts);

		matrix[start][end] = 1;
	}

	public void addEdge(T dependency, T dependent) {

		addEdge(getIndex(dependency), getIndex(dependent));
	}

	/*
	 * public void displayVertex(INT v) { System.out.print(vertexList[v].label);
	 * }
	 */

	private int getIndex(T item) {

		int idx = -1;

		for (int i = 0; i < vertexList.length; i++) {

			if (item.equals(vertexList[i])) {
				idx = i;
				break;
			}
		}

		if (idx == -1)
			throw new IllegalArgumentException(String.format("Item \"%s\" its not in vertex list!", item));

		return idx;
	}

	public T[] topo() throws RuntimeException// Topological sort
	{
		while (numVerts > 0) // while vertices remain,
		{
			// get a vertex with no successors, or -1
			int currentVertex = noSuccessors();

			if (currentVertex == -1) // must be a cycle
			{
				throw new RuntimeException("ERROR: Graph has cycles\nVertex: " + vertexList[numVerts]);
				// log("ERROR: Graph has cycles");
				// return null;
			}

			// insert vertex label in sorted array (start at end)
			sortedArray[numVerts - 1] = vertexList[currentVertex];

			deleteVertex(currentVertex); // delete vertex
		}

		return sortedArray;

	}

	public int noSuccessors() // returns vertex with no successors (or -1 if no
								// such verts)
	{
		boolean isEdge; // edge from row to column in adjMat

		int row = 0;
		int col = 0;

		StringBuffer sb = null;

		for (row = 0; row < numVerts; row++) {

			sb = new StringBuffer();
			isEdge = false; // check edges

			for (col = 0; col < numVerts; col++) {

				sb.append(vertexList[col]);
				sb.append(" -> ");

				if (matrix[row][col] > 0) // if edge to another,
				{
					isEdge = true;
					break; // this vertex has a successor try another
				}
			}

			if (!isEdge) // if no edges, has no successors
				return row;
		}

		return -1; // no
	}

	public void deleteVertex(int delVert) {
		if (delVert != numVerts - 1) // if not last vertex, delete from
										// vertexList
		{
			for (int j = delVert; j < numVerts - 1; j++)
				vertexList[j] = vertexList[j + 1];

			for (int row = delVert; row < numVerts - 1; row++)
				moveRowUp(row, numVerts);

			for (int col = delVert; col < numVerts - 1; col++)
				moveColLeft(col, numVerts - 1);
		}
		numVerts--; // one less vertex
	}

	private void moveRowUp(int row, int length) {
		for (int col = 0; col < length; col++)
			matrix[row][col] = matrix[row + 1][col];
	}

	private void moveColLeft(int col, int length) {
		for (int row = 0; row < length; row++)
			matrix[row][col] = matrix[row][col + 1];
	}

}
